package com.jml.LinkedList;

import java.util.LinkedList;

public class ExtLinkedList<E> {

	//链表实际存储元素
	 int size;
	//头结点  为了查询
	 Node<E> first;
	//尾节点  为了添加
	 Node<E> last;

	public void add(E e){
		Node node = new Node();
		node.item=e;
		//如果是第一个元素
		if(first == null){
			node.prev=null;
			node.next=null;
			first = node;
		}else{
			node.prev = last;
			last.next = node;
		}
		last = node;
		size++;
	}

	public Node get(int index){
		checkElementIndex(index);
		return getNodeByIndex(index);

	}

	public Node  getNodeByIndex(int index){
		//折半查找
		if (index < (size >> 1)) {
			Node<E> x = first;
			for (int i = 0; i < index; i++) {
				x = x.next;
			}
			return x;
		} else {
			Node<E> x = last;
			for (int i = size - 1; i > index; i--){
				x = x.prev;
			}
			return x;
		}
	}

	private void checkElementIndex(int index) {
		if (!(index >= 0 && index < size))
			throw new IndexOutOfBoundsException("");
	}

	public void add(int index,E e) {
		checkElementIndex(index);
		Node oldNode = get(index);
		Node oldNodePre = null;
		Node<E> newNode = new Node<>();
		newNode.item = e;
		if(oldNode!=null){
			oldNodePre = oldNode.prev;
			//插入的是第一个节点
			if(oldNodePre ==null){
				newNode.next = first;
				first.prev = newNode;
				first = newNode;
				size++;
				return;
			}
			newNode.prev=oldNodePre;
			newNode.next = oldNode;
			//-------------------
			oldNode.prev = newNode;
			oldNodePre.next = newNode;
		}else{
			newNode.prev=last;
			last.next = newNode;
			last = newNode;
		}
		size++;
	}

	public E remove(int index){
		Node deleteNode = getNodeByIndex(index);

		Node prevNode = deleteNode.prev;
		Node nextNode = deleteNode.next;
		if(prevNode==null&&nextNode==null){
			first=null;
			last=null;
		}else if(prevNode==null){
			Node tempNode = first.next;
			first=tempNode;
			first.prev = null;
		}else if(nextNode ==null){
			Node tempNode = last.prev;
			last =tempNode;
			last.next = null;
		}else{
			prevNode.next = nextNode;
			nextNode.prev = prevNode;
		}
		size--;
		return (E) deleteNode.item;
	}

}
